1. Field of the Invention
The present invention relates in general to methods and apparatus for electronic communications, and particularly to a system and method for controlling traffic on a ring topology network.
2. Background Information
There is a rapidly increasing demand for very high performance shared access to distributed data, for multiprocessors, networked workstation clusters, distributed databases, etc. The objective is to satisfy this demand at the lowest long-term cost. To do that, a wide range of interconnect technologies are available. These include switch networks, busses, simple daisy-chain or ring connections and combinations of switch and ring topologies. In systems where there are a large number of nodes, a ring topology such as the Scalable Coherent Interface (SCI) has been well received.
SCI was developed by a number of high-performance-bus designers and system architects. The SCI protocol was designed to eliminate dependencies that can cause deadlocks, and to include simple mechanisms that assure fair allocation of resources and livelock avoidance. It was recognized that very soon microprocessor speeds would exceed the capability of any bus to support significant multiprocessing. The SCI protocol includes two fundamental design choices which make it especially adapted to high speed data communication between a large number of nodes.
The first design choice was to make signaling speed independent of the size of the system. Other bus protocols require a node to wait one entire bus cycle before sending the next signal. In contrast, an SCI node does not wait for each signal to propagate before transmitting the next signal. As a result, SCI signaling speed is independent of the size of the system. Each SCI communication is performed by sending packets, each packet containing an address, a command, and data as appropriate. Each packet is then either accepted and stored in the responders' queues or is discarded (if there is not sufficient space). An echo packet tells the requestor whether the Send packet can be discarded or that it was not accepted and must be retransmitted. A similar handshake occurs in response.
In the SCI protocol, echo packets provide a handshake that passes responsibility for a packet from one buffer to the next as the packet flows through the interconnect. All other SCI packets have a 16-byte header that contains address information and a command transaction identifier. Response packets also include status information. The size of any packet that may need to be stored in queues is some multiple of 16 bytes, thereby simplifying storage management at very high speeds. An echo packet is an 8-byte subset of the header. Thus, the echo is not a confirmation of the completion of the sub-action. Instead, requests are confirmed end-to-end by response packets.
The second SCI design choice was to use multiple signal paths (links) so that multiple independent transfers can take place concurrently. For higher performance, separate links can be used for each processor, memory, or I/O device.
One factor affecting communications performance in any network communication protocol is latency. Latency is the delay between a request for data and the receipt of the requested data. This delay is primarily due to signal propagation at the finite speed of light, but is augmented by both technology-dependent and implementation-dependent factors. Thus, as technology advances, latency remains almost the same, as it is dominated by its speed of light component. The cost of accessing information from a given distance, however, is measured in missed opportunities, which increase as technology advances. Higher processor clock frequency increases the amount of available resources wasted during any clock period. In addition, the amount of data that can be moved during the latency period increases with transmission bandwidth. The cost of latency is therefore increasingly significant, and while communication bandwidth increases with technology and becomes less expensive, latency, measured in processor clock cycles, becomes more expensive.
SCI attempts to reduce latency by running the links continuously, sending Idle symbols when no packets are being transmitted. In this way a receiver can remain perfectly synchronized at all times, ready for action. SCI packets do not need the prologue that is essential for Ethernet or similar networks. Idle symbols also carry information about the priorities of other nodes, as well as go-bits. Go-bits act like tokens, helping ensure fair use of the links (in order to avoid starvation or deadlock). An SCI node must, however, maintain dual queues in order to keep responses independent of requests. Without dual queues, excessive requests prevent the sending of responses, resulting in deadlock.
Since introduction of the SCI standard in 1994, there have been several papers published proposing improvements in the SCI architecture and protocols. For example, David Gustavson and Qiang Li describe a 2-bit priority scheme in "Local Area Multiprocessor: The Scalable Coherent Interface" (ftp://ftp.SCIzzL.com/u/SCIzzLdocs/WesconLAMP/optvSCCIzzLb.pdf 1995). In another article Dan Picker, Ronald Fellman and Paul Chau discuss an extension to the SCI flow control protocol ("An Extension to the SCI Flow Control Protocol for Increased Network Efficiency", IEEE/ACM Transaction on Networking, February 1996). This activity reflects the fact that despite its revolutionary architecture and performance, there are limiting factors in the current SCI standard.
Contemporary efforts to improve SCI tend to be narrowly focused and threaten to proliferate new SCI-like standards, with each standard being crafted for a particular user community. Two examples of such proposed standards are outlined in the RT-SCI and Serial-Express proposals, described by David James and David Gustavson in "Draft Proposals for Real-Time Transactions on SCI", and "Serial Express--A Scalable Gigabit Extension to Serial Bus", IEEE Standards Department, draft .600, Apr. 8, 1996). Neither approach, however, adequately addresses the shortcomings of the current SCI bandwidth allocation protocol.
These problems can be overcome by replacing the "go-bits/Idle symbols" scheme with an adaptive bandwidth sharing algorithm as described below.